package com.bitauto.i.commonUtils.arithmetic;

import java.util.HashSet;
import java.util.Set;

/**
 * 判断链表是否有环
 */
public class LinkListHasCycle {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 快慢指针
     * @param head
     * @return
     */
    public boolean hasCycle1(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next;
        int count = 0;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
            count++;
        }
        System.out.println("hasCycle1 count:"+count);
        return true;
    }

    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode current = head;
        int count = 0;
        while (current != null) {
            if (visited.contains(current)) {
                System.out.println("hasCycle count:"+count);
                return true;
            }
            visited.add(current);
            current = current.next;
            count++;
        }
        System.out.println("hasCycle count:"+count);
        return false;
    }

    public static void main(String[] args) {
        LinkListHasCycle solution = new LinkListHasCycle();

        // 创建有环链表
        ListNode head = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node0 = new ListNode(0);
        ListNode node1 = new ListNode(1);
        ListNode node4 = new ListNode(4);

        head.next = node2;
        node2.next = node0;
        node0.next = node1;
        node1.next = node4;
        node4.next = node2; // 形成环

        System.out.println("Has cycle: " + solution.hasCycle1(head)); // 输出 true
        System.out.println("Has cycle: " + solution.hasCycle(head)); // 输出 true

        // 创建无环链表
       /* ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);

        System.out.println("Has cycle: " + solution.hasCycle1(head2)); */// 输出 false
    }

}
